package dynamic.barcutting;

/**
 * 自顶向下的动态规划算法处理钢条切割问题
 *
 * @author 罗俊华
 * @date 2021/7/21 - 9:09 上午
 */
public class TopToDownDynamic {

    public static int getMaxProfit(int[] lengthMappingProfit, int length) {

//        加缓存，用于存储指定length对应的最大收益，避免重复求解相同子问题
        int[] cache = new int[length + 1];

        for (int i = 1; i <= length; i++) {
            cache[i] = Integer.MIN_VALUE;
        }

        return getMaxProfit(lengthMappingProfit, length, cache);
    }

    private static int getMaxProfit(int[] lengthMappingProfit, int length, int[] cache) {

        if (cache[length] != Integer.MIN_VALUE) {
            // 缓存命中
            return cache[length];
        }

        if (length == 0) {
            return 0;
        }

        int profit = 0;
        int leftProfit = 0;
        for (int i = 1; i <= length; i++) {
//            profit = Math.max(profit, lengthMappingProfit[i] + getMaxProfit(lengthMappingProfit, length - i, cache));

            leftProfit = 0;

            // 使用以下的改进之后，使得此算法能计算任意长度的钢条最大收益，不再受 lengthMappingProfit 长度的限制
            if (i < lengthMappingProfit.length) {

                leftProfit = lengthMappingProfit[i];

            } else if (cache[i] != Integer.MIN_VALUE) {

                leftProfit = cache[i];
            }

            profit = Math.max(profit, leftProfit + getMaxProfit(lengthMappingProfit, length - i, cache));

        }

        cache[length] = profit;

        return profit;
    }

}
